[JS/백준]{BFS}(2146) 다리 만들기

문제 설명

30분정도 문제를 뚫어져라 쳐다본결과 풀이감이 잡히질 않아서 다른분들 코드를 참고했다.

우선 문제를 풀려면 섬을 넘버링 해야한다 1번섬, 2번섬, 3번섬 이렇게 board에 적용한다.

넘버링하는 도중에 해당 좌표 4방향중에 바다가 있으면 edgeSea 배열에 추가한다 (가장 자리)

그 후 모든 가장자리 위치에서 다리를 만들어주는데 다리값을 해당 섬의 넘버 값을 넣어준다

만약 다리를 건설중에 다른 넘버 즉 다른 섬이나 다리를 만나면 최소거리를 비교해서 갱신한다.

// 초기 상태 board    // 넘버링 후 board   // 다리를 건설후 board  // 다리의 길이 distance
1 1 1 0 0 0 0 1 1 1   1 1 1 0 0 0 0 2 2 2   1 1 1 1 1 2 2 2 2 2   0 0 0 1 2 2 1 0 0 0
1 1 1 1 0 0 0 0 1 1   1 1 1 1 0 0 0 0 2 2   1 1 1 1 1 1 2 2 2 2   0 0 0 0 1 2 2 1 0 0
1 0 1 1 0 0 0 0 1 1   1 0 1 1 0 0 0 0 2 2   1 1 1 1 1 1 2 2 2 2   0 1 0 0 1 2 2 1 0 0
0 0 1 1 1 0 0 0 0 1   0 0 1 1 1 0 0 0 0 2   1 1 1 1 1 1 1 2 2 2   1 1 0 0 0 1 2 2 1 0
0 0 0 1 0 0 0 0 0 1   0 0 0 1 0 0 0 0 0 2   1 1 1 1 1 1 1 2 2 2   2 2 1 0 1 2 3 2 1 0
0 0 0 0 0 0 0 0 0 1   0 0 0 0 0 0 0 0 0 2   1 1 1 1 1 3 2 2 2 2   3 3 2 1 2 2 3 2 1 0
0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0   1 1 1 1 3 3 3 2 2 2   4 4 3 2 1 1 2 3 2 1
0 0 0 0 1 1 0 0 0 0   0 0 0 0 3 3 0 0 0 0   3 3 3 3 3 3 3 3 2 2   4 3 2 1 0 0 1 2 3 2
0 0 0 0 1 1 1 0 0 0   0 0 0 0 3 3 3 0 0 0   3 3 3 3 3 3 3 3 3 2   4 3 2 1 0 0 0 1 2 3
0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0   3 3 3 3 3 3 3 3 3 2   5 4 3 2 1 1 1 2 3 4

풀이 코드

function makeBridge(edgeSea) {
  let result = Infinity;

  while (edgeSea.length) {
    const [x, y, number] = edgeSea.shift();

    for (let k = 0; k < 4; k++) {
      let nx = x + dx[k];
      let ny = y + dy[k];
      if (0 <= nx && 0 <= ny && nx < n && ny < n) {
        if (!board[nx][ny]) {
          board[nx][ny] = number;
          distance[nx][ny] = distance[x][y] + 1;
          edgeSea.push([nx, ny, number]);
        } else if (board[nx][ny] !== number) {
          result = Math.min(result, distance[nx][ny] + distance[x][y]);
        }
      }
    }
  }
  console.log(result);
}

function numbering() {
  let edgeSea = [];
  let number = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 1 && !visited[i][j]) {
        visited[i][j] = true;
        board[i][j] = number;

        let q = [[i, j]];

        while (q.length) {
          const [x, y] = q.shift();

          for (let k = 0; k < 4; k++) {
            let nx = x + dx[k];
            let ny = y + dy[k];

            if (0 <= nx && 0 <= ny && nx < n && ny < n && !visited[nx][ny]) {
              if (board[nx][ny] === 1) {
                q.push([nx, ny]);
                board[nx][ny] = number;
                visited[nx][ny] = true;
              } else if (board[nx][ny] === 0) {
                edgeSea.push([x, y, number]);
              }
            }
          }
        }
        number++;
      }
    }
  }
  makeBridge(edgeSea);
}

let input = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +input[0];
const board = input.slice(1).map((str) => str.split(" ").map(Number));

let visited = Array.from(Array(n), () => new Array(n).fill(false));
let distance = Array.from(Array(n), () => new Array(n).fill(0));

const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];

numbering();